package msb.class01;

import common.sort.AbstractSort;
import common.util.ArrayUtil;

/**
 * 选择排序
 *
 * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
 * 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 * 重复第二步，直到所有元素均排序完毕。
 * <p>
 * 0 ~ N-1  找到最小值，在哪，放到0 位置上
 * 1 ~ n-1  找到最小值，在哪，放到1 位置上
 * 2 ~ n-1  找到最小值，在哪，放到2 位置上
 *
 * 时间复杂度 O(n^2)
 */
public class Code01_SelectionSort extends AbstractSort {

    public void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            ArrayUtil.swap(arr, i, minIndex);
        }
    }

    public static void main(String[] args) {
        Code01_SelectionSort sort = new Code01_SelectionSort();
        sort.check();
    }

}
